Alexei Leonov sinh ngày 30 tháng 5 năm 1934 tại Listvyanka, vùng (krai) Tây Siberia, Cộng hòa XHCH Xô viết Liên bang Nga. Ông nội của ông bị cưỡng bách phải chuyển tới Siberia vì liên can tới Cách mạng Nga năm 1905. Alexei là con thứ 8 trong số 9 người con còn sống sau sinh của bà Yevdokia (nhũ danh Sotnikova) và ông Arkhip, làm nghề thợ điện và thợ mỏ.

Năm 1936, cha của Alexei bị bắt giữ và bị tuyên bố là "kẻ thù của nhân dân". Leonov viết trong tự truyện: "Ông ấy không đơn độc: nhiều người cũng bị bắt. Đó là một nỗ lực tận tâm của nhà chức trách nhằm loại bỏ bất cứ ai biểu hiện tính độc lập quá cao hay có tính cách mạnh mẽ. Đó là những năm thanh trừng của Stalin. Nhiều người biến mất trong các trại gulag và không bao giờ trở lại nữa."

Gia đình Leonov chuyển tới sống cùng với một người chị đã lập gia đình Kemerovo. Cha của ông đoàn tụ với gia đình ở Kemerovo sau khi được thả, và được nhận một khoản tiền đền bù vì bị ngồi tù oan sai. Leonov dùng tài năng nghệ thuật để kiếm thêm thức ăn cho gia đình. Ông bắt đầu nghề vẽ với những bức tranh vẽ hoa cỏ và về sau vẽ tranh phong cảnh trên toan.

Chính quyền Xô-viết khuyến khích cư dân chuyển tới sinh sống ở Prussia đã nằm dưới quyền kiểm soát của Liên Xô, vì vậy, vào năm 1948 cả gia đình chuyển tới Kaliningrad. Leonov tốt nghiệp trường trung học năm 1953. Ông ghi danh vào Học viện Nghệ thuật ở Riga, Lativa nhưng quyết định không nhập học vì học phí quá cao. Leonov chuyển hướng sang nhập học một trường phi công dự bị Ukraine ở Kremenchug. Ông thực hiện chuyến bay độc lập đầu tiên vào tháng 5 năm 1955. Trong khi vẫn nuôi dưỡng đam mê mỹ thuật bằng cách học thêm ở Riga, Leonov bắt đầu khóa huấn luyện chuyên sâu để trở thành phi công máy bay chiến đấu tại Trường Phi công Không lực cao cấp Chuguev tại Cộng hòa Xã hội chủ nghĩa Xô viết Ukraina.

Vào ngày 30 tháng 10 năm 1957, Leonov tốt nghiệp với bằng danh dự và được phong làm trung úy tại Trung đoàn Không quân nhảy dù số 113, trực thuộc Sư đoàn Không quân Kỹ thuật số 10, Tập đoàn Không quân số 69 đóng tại Kiev. Vào ngày 13 tháng 12 năm 1959, ông kết hôn với Svetlana Pavlovna Dozenko. Hôm sau, ông chuyển tới Đông Đức để nhận nhiệm vụ mới tại Trung đoàn Trinh sát số 294, thuộc Tập đoàn Không quân số 24.